package 题目集.单调栈or队列.单调栈;

import org.junit.Test;

/**
 * 给一个数组，求所有子区间的最小值之和
 * https://leetcode.cn/problems/sum-of-subarray-minimums/description/
 */
public class 子数组的最小值之和 {
    /**
     * 暴力解：
     *      枚举每一个区间，求区间内的最小值，然后求和
     *      时间复杂度：O(n^2)
     * 单调栈解：
     *      以下标i为最小值的区间有哪些？
     *          左边第一个比a[i]小的数的下标l到i都以a[i]为最小值，（不包含l）
     *          和右边第一个比a[i]小的数的下标r到i都以a[i]为最小值,（不包含l）
     *          以i为最小值的总数：(i-l)*(r-i)
     *       可以通过单调栈求出l和r，但如果存在相同的最小值，会导致重复计算。所以当发生重复时，左侧重复值的右边界为右侧的重复值下标。
     */
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] stack = new int[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            //如果左侧>=当前值出栈，正常来讲==是不出栈的，这里出栈是为了去除重复计算
            // 并将弹出的右侧第一个比自己小值设置为当前下标
            while (top != -1 && arr[stack[top]] >= arr[i]) {
                right[stack[top--]] = i;
            }
            //如果栈中还有元素，那么栈中的元素就是自己左侧第一个比自己小的元素。
            left[i] = top == -1 ? -1 : stack[top];  //这个-1很巧妙.因为是个数包含自身的。在计算个数时，直接减去left[i]即可
            stack[++top] = i;
        }
        while (top != -1) { //右侧没有比自己小的元素
            right[stack[top--]] = n;     //这个n很巧妙，个数是包含自身的。在计算个数时，直接right[i]-i即可
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += (long) (i - left[i]) * (right[i] - i) * arr[i];    //以i为最小值的区间个数
            res %= 1000000007;
        }
        return (int) (res % 1000000007);
    }
    @Test
    public void test(){
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4}));
    }
}
